import java.util.HashMap;

public class MapSum1 {

    class Trie {
        int val;
        Trie[] next = new Trie[26];
    }

    HashMap<String, Integer> map;
    Trie trie;
    public MapSum1() {
        map = new HashMap<>();
        trie = new Trie();
    }

    public void insert(String key, int val) {
        int delta = val - map.getOrDefault(key, 0);
        Trie node = trie;
        for (char c : key.toCharArray()) {
            if (node.next[c - 'a'] == null) node.next[c - 'a'] = new Trie();
            node.next[c - 'a'].val += delta;
            node = node.next[c - 'a'];
        }
        map.put(key, val);
    }

    public int sum(String prefix) {
        Trie node = trie;
        for (char c : prefix.toCharArray()) {
            if (node.next[c - 'a'] == null) return 0;
            node = node.next[c - 'a'];
        }
        return node.val;
    }
}
